The principle of iterative decoders is described, for example, in J. Hagenauer, E. Offer, and L. Papke, “Iterative decoding of binary block and convolutional codes”, IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 429-445, March 1996. Typically, iterative decoding may be based on exchange of de-correlated extrinsic information between soft-input soft-output (SISO) constituent decoders.
FIG. 1A illustrates an example implementation of iterative decoding using such a setup of constituent SISO decoders 11 and 13 which may be suitable for decoding of e.g. a turbo code with rate 1/2 constituent codes.
In this example, received intrinsic soft values representing two code bits (code symbols in more general cases) are input to the first SISO decoder 11 (Decoder 1) as illustrated by reference numbers 41 and 42. Decoder 1 outputs extrinsic soft values for each information bit (or more generally each information symbol) as illustrated by reference number 22, and the extrinsic soft values are interleaved in an interleaver 12.
The interleaved extrinsic soft values are input to the second SISO decoder 13 (Decoder 2) as illustrated by reference number 23, together with the received intrinsic soft values as illustrated by reference numbers 43 and 44 (after interleaving as applicable depending on the particular code setup). Decoder 2 outputs extrinsic soft values for each information bit as illustrated by reference number 24. The extrinsic soft values are deinterleaved in a deinterleaver 14 and fed back to Decoder 1 to serve as input of a second iteration as illustrated by reference number 21, together with the received intrinsic soft values. In the first iteration the input 21 is fed with neutral soft values.
This iterative exchange of extrinsic information gradually improves the reliability of the extrinsic information. After an appropriate number of iterations, a hard decision 30 may be taken in relation to each information bit in a decision unit 15 based on extrinsic soft values output from Decoder 2.
The operation of each of the SISO modules 11, 13 of FIG. 1A may typically be illustrated using a trellis diagram. FIG. 1B illustrates part of an example trellis diagram 100 representing an example constituent code of a turbo code. In this particular example, each stage of the trellis has four nodes (101, 103, 105, 107 for the first stage, 111, 113, 115, 117 for the second stage, etc.), where each node represents a state of the corresponding encoder. Furthermore, this example trellis has two incoming paths to each node (e.g. 111a, 111b for node 111). Trellis diagrams are very well known in the art and will therefore not be described in greater detail.
The SISO modules themselves may consist of (variants of) the BCJR (Bahl, Cocke, Jelinek, Raviv) algorithm (known from L. R. Bahl et al., “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Trans. Inf. Theory, vol. 20, no. 2, pp. 284-287, March 1974 and from P. Robertson, P. Höher, and E. Villebrun, “A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain”, Proc. IEEE Intl. Conf. Comm., Seattle, June 1995, pp. 1009-1013 for the logarithmic domain).
However, the BCJR algorithm and its variants suffer from a considerable amount of complexity. To fulfill throughput requirements of some applications an implementation in dedicated hardware may often be required as well as advanced parallelization techniques.
Another possibility for the SISO modules is (variants of) an approach based on the traditional Viterbi algorithm, namely the soft-output Viterbi algorithm (SOVA) disclosed in J. Hagenauer and P. Höher, “A Viterbi algorithm with soft-decision output and its applications”, Proc. IEEE Globecom, Dallas, November 1989, pp. 1680-1686.
Typically, SOVA provides soft output values at a lower complexity cost than the BCJR algorithm. Another advantage of SOVA is a reduction in latency compared to BCJR. Latency of SOVA basically depends on the depth of the decoding window (as known from traditional Viterbi decoding). SOVA may also have the advantage of less parallelization required. In some situations, however, the SOVA suffers from a worse error rate performance than the BCJR algorithm.
As known in the art, SOVA may initially assign a reliability value L to each node of the trellis, where the reliability value depends on the path metrics of the incoming paths of the node. For a trellis with two incoming paths to each node, the initial reliability value may be the absolute value of the difference between the metrics of the two incoming paths, L←Δ=|M(s′)−M(s″)|, where s′ and s″ are the two incoming paths and M(s) is the path metric of path s. The path metric may for example, be a cumulative metric.
In some applications SOVA uses the following update rule, often termed the Hagenauer rule, for the reliability values:
Lk-U(s)←min(Lk(s),Lk-U(s)) if uk-U(s)≠uk-U(c) and
Lk-U(s) unchanged otherwise,
where Lk-U(s) denotes the reliability value of the node of a surviving path at stage k-U. The notations used may be illustrated in a schematic trellis diagram as the one shown in FIG. 1C.
In the example of FIG. 1C, the SOVA applies a sliding window 120 of length U, which is currently in position k. A surviving path s for the uppermost node 124 at stage k is denoted with reference number 121 and has a corresponding decision bit (or more generally—decision symbol) uk-U(s), denoted by reference number 126, at stage k-U. Its concurrent path c is denoted with reference number 122 and has a corresponding decision bit uk-U(c), denoted by reference number 127, at stage k-U. At stage k-1 the node of the surviving path has a concurrent path denoted by reference number 123.
Thus, if the decision bits 126 and 127 differs and if the reliability value of the node 124 of the surviving path at stage k is lower than the reliability value of the node 125 of the surviving path at stage k-U, the Hagenauer rule suggests that the reliability value of node 125 should be replaced by the reliability value of node 124.
We denote a SOVA applying the Hagenauer update rule as HR-SOVA. Hardware architectures using the Hagenauer rule are know from E. Yeo et al., “A 500 Mbit/s soft output Viterbi decoder”, IEEE J. Solid-State Circuits, vol. 38, no. 7, pp. 1234-1241, July 2003.
The update rule applied for the reliability values affects the quality (e.g. accuracy) of the extrinsic soft output values and thus the overall performance of the iterative decoder.
Another reliability value update rule that may be used with SOVA in the SISO modules is the Battail rule known from G. Battail, “Pondération des symboles décodés par l'algorithme de Viterbi”, Annales des Télécommuncations, No. 1-2, pp. 31-38, January-Febuary 1987. We denote a SOVA applying the Battail update rule as BR-SOVA.
The Battail rule is equivalent in terms of performance to max-log-MAP (maximum aposteriori) decoding as illustrated in M. Fossorier et al., “On the equivalence between SOVA and max-log-MAP decodings”, IEEE Comm. Letters, vol. 2, no. 5, pp. 137-139, May 1998. However, the complexity increase of this update rule compared to the Hagenauer rule is troublesome, and prevents or at least severely obstructs any hardware implementations. The complexity of the Battail rule also counteracts the complexity reduction achieved by using SOVA in stead of BCJR.
For HR-SOVA only the metric differences along the survivor path are considered for updating the reliability values. For BR-SOVA the metric differences along the concurrent path are also used in the updating. This is the cause of the, potential many-fold, increase in complexity of BR-SOVA.
The Battail rule for updating of reliability values may be expressed as:
Lk-U(s)←min(Lk(s),Lk-U(s)) if uk-U(s)≠uk-U(c) and
Lk-U(s)←min(Lk(s)+Lk-U(c),Lk-U(s)) if uk-U(s)=uk-U(c).
The Battail update rule may be illustrated in a schematic trellis diagram as the one shown in FIG. 1D.
In the example of FIG. 1D, the SOVA applies a sliding window 130 of length U, which is currently in position k. A surviving path s for the uppermost node 133 at stage k is denoted with reference number 131 and has a corresponding decision bit uk-U(s), denoted by reference number 136, at stage k-U. Its concurrent path c is denoted with reference number 132 and has a corresponding decision bit uk-U(c), denoted by reference number 137, at stage k-U.
Now, if the decision bits 136 and 137 are equal, the Battail rule suggests that the reliability value of node 138 may be replaced by a sum of the reliability value of node 133 and the reliability value of node 139. Thus, to evaluate of this replacement should take place and, if applicable, perform the replacement, the reliability value of node 139 must first be determined which involves evaluation of the secondary concurrent paths (134, 135, etc.) and results in a complexity increase and a latency increase.
The size and complexity of implementations of a turbo decoder may be an important implementation parameter as well as latency. At the same time, acceptable error rate performance should typically be achieved.
In some scenarios, parallelization is required to meet latency requirements. This may particularly be the case if BCJR-like algorithms are applied. Such parallelization further enhances the importance of small size modules.
On the other hand, low-latency SOVA-type algorithms require a complicated update procedure if MAP baseline performance is to be fully maintained as elaborated on above.
Thus, there is a need for improved SISO algorithms for decoding methods and decoders. Preferably, the improved algorithms should have low latency, low complexity and good error rate performance.